home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / LDB171.ARJ / BINDER.CPP next >
C/C++ Source or Header  |  1992-07-10  |  19KB  |  1,017 lines
  1. /*
  2.     binder.cpp -- Loose Data Binder v 1.7
  3.  
  4.     (C) Copyright 1992  John W. Small
  5.     All rights reserved
  6.  
  7.     PSW / Power SoftWare
  8.     P.O. Box 10072
  9.     McLean, Virginia 22102 8072 USA
  10.     (703) 759-3838
  11. */
  12.  
  13. #include <string.h>
  14. #include <fstream.h>
  15. #include "binder.hpp"
  16.  
  17. static  Binder  comPRegistry(BDR_DDELETE);
  18. Binder& Binder::comPv = comPRegistry;
  19.  
  20. unsigned Binder::comPID(BDRcomP comP)
  21. {
  22.     unsigned i = 0;
  23.     BDRcomP *CP;
  24.  
  25.     while ((CP = (BDRcomP *)comPv.atGet(i++))
  26.         != (BDRcomP *)0)
  27.         if (*CP == comP)
  28.             return i;
  29.     return 0;
  30. }
  31.  
  32. BDRcomP Binder::comPLU(unsigned ID)
  33. {
  34.     BDRcomP *CP = (BDRcomP *)comPv.atGet(--ID);
  35.     return (CP? *CP : BDRcomP0);
  36. }
  37.  
  38. int Binder::initData(unsigned flags, unsigned maxNodes,
  39.     unsigned limit, unsigned delta)
  40. {
  41.     curNode = first = nodes = 0;
  42.     comP = BDRcomP0;
  43.  
  44. /*
  45.     The following relationships are maintained
  46.     during operation of a binder:
  47.  
  48.     1 <= delta <= lowLimit <= limit <= maxNodes
  49.         <= BDR_MAXNODES
  50.     lowThreshold = lowLimit - delta;
  51. */
  52.  
  53.     if (maxNodes > BDR_MAXNODES)
  54.         maxNodes = BDR_MAXNODES;
  55.     if (limit > maxNodes)
  56.         limit = maxNodes;
  57.     if (delta > limit)
  58.         delta = limit;
  59.     if (!delta)  {
  60.         delta = 1;
  61.         if (limit < delta)
  62.             limit = delta;
  63.         if (maxNodes < limit)
  64.             maxNodes = limit;
  65.     }
  66.     if ((linkS = new voiD[limit]) == voiDV0)  {
  67.         this->limit = lowLimit = lowThreshold
  68.             = this->delta = this->maxNodes
  69.             = this->flags = 0;
  70.         return 0;
  71.     }
  72.     else  {
  73.         this->limit = limit;
  74.         this->delta = delta;
  75.         this->maxNodes = maxNodes;
  76.         lowLimit = limit;
  77.         lowThreshold = lowLimit - delta;
  78.         this->flags = (flags | BDR_SORTED);
  79.         return 1;
  80.     }
  81. }
  82.  
  83. void Binder::destruct()
  84. {
  85.     if (flags & BDR_DDELETE)
  86.         allDel();
  87.     else
  88.         allRmv();
  89.     if (linkS)  {
  90.         delete linkS;
  91.         linkS = voiDV0;
  92.     }
  93. }
  94.  
  95. void Binder::sberror(const char * msg)
  96. {
  97.     if (Binder::streamDebug)
  98.         cerr << endl << msg << endl;
  99. }
  100.  
  101. void Binder::berror(const char * msg)
  102. {
  103.     if (streamDebug)
  104.         cerr << endl << msg << endl;
  105. }
  106.  
  107. void Binder::store(ostream& os)
  108. {
  109.     unsigned i;
  110.  
  111.     os << maxNodes << BDRendm << limit << BDRendm
  112.         << delta << BDRendm << nodes << BDRendm
  113.         << curNode << BDRendm << flags << BDRendm
  114.         << comPID(comP) << BDRendm;
  115.     if (!os)
  116.         berror("unable to store Binder "
  117.             "data on stream");
  118.     else for (i = 0; i < nodes; i++)
  119.         Dstore(os,atGet(i));
  120. }
  121.  
  122. BindeR Binder::load(istream& is, BindeR thiS)
  123. {
  124.     unsigned maxNodes, limit, delta, nodes;
  125.     unsigned curNode, flags, comPid;
  126.     unsigned i, newed;
  127.  
  128.     is >> maxNodes >> BDRnextm >> limit >> BDRnextm
  129.         >> delta >> BDRnextm >> nodes >> BDRnextm
  130.         >> curNode >> BDRnextm >> flags >> BDRnextm
  131.         >> comPid >> BDRnextm;
  132.     if (!is)  {
  133.         sberror("unable to load Binder "
  134.             "data from stream");
  135.         return BindeR0;
  136.     }
  137.     flags |= BDR_DDELETE;
  138.     //reloaded nodes are dynamic!
  139.     if (thiS)
  140.         newed = 0;
  141.     else  {
  142.         if ((thiS = new Binder(initVFTsOnly))
  143.             == BindeR0)  {
  144.             sberror("unable to construct "
  145.                 "new Binder for loading");
  146.             return BindeR0;
  147.         }
  148.         newed = 1;
  149.     }
  150.     if (!thiS->initData(flags,maxNodes,limit,delta))  {
  151.         sberror("unable to initialize Binder "
  152.             "from reloaded stream data");
  153.         if (newed)
  154.             delete (voiD) thiS;
  155.         return BindeR0;
  156.     }
  157.     for (i = 0; i < nodes; i++)
  158.         (void) thiS->insQ(thiS->Dload(is));
  159.     thiS->setCurNode(curNode);
  160.     thiS->setComP(comPLU(comPid));
  161.     return thiS;
  162. }
  163.  
  164. int Binder::vload(const char * filename,
  165.     BDRsloaD sloaD, voiD thiS)
  166. {
  167.     ifstream is(filename);
  168.  
  169.     if (is)  {
  170.         int ok = ((*sloaD)(is,thiS)? 1 : 0);
  171.         if (!ok)
  172.             initData(0U,0U,0U,0U);
  173.         is.close();
  174.         return ok;
  175.     }
  176.     else  {
  177.         initData(0U,0U,0U,0U);
  178.         berror("unable to load Binder from "
  179.             "file ...");
  180.         berror(filename);
  181.         return 0;
  182.     }
  183. }
  184.  
  185. int  Binder::streamDebug = 0;
  186. char Binder::memberTermChar = '\n';
  187.  
  188. void  Binder::RegisterComP(BDRcomP comP)
  189. {
  190.     if (comP) if (!comPID(comP))  {
  191.         BDRcomP *CP = new BDRcomP;
  192.         if (CP)  {
  193.             *CP = comP;
  194.             if (!comPv.insQ(CP))
  195.                 delete CP;
  196.         }
  197.     }
  198. }
  199.  
  200. Binder::Binder(voiDV argv, unsigned argc, unsigned flags)
  201. {
  202.    if (initData(flags,BDR_MAXNODES,argc,BDR_DELTA))
  203.     if (argv)
  204.         if (argc > 0)
  205.             while (argc--)
  206.                 (void) push(argv[argc]);
  207.         else
  208.             for (argc = 0; insQ(argv[argc]);
  209.                 argc++)
  210.                 /* null stmt */;
  211. }
  212.  
  213. int Binder::save(const char *filename)
  214. {
  215.     if (flags & BDR_DSTORE)  {
  216.         ofstream os(filename);
  217.         if (os)  {
  218.             store(os);
  219.             os.close();
  220.             return 1;
  221.         }
  222.         else  {
  223.             berror("unable to save Binder in "
  224.                 "file ...");
  225.             berror(filename);
  226.         }
  227.     }
  228.     return 0;
  229. }
  230.  
  231. voiDV Binder::vector()
  232. {
  233.     voiDV V = voiDV0;
  234.  
  235.     if (nodes) if ((V = new voiD[nodes+1]) != voiDV0)  {
  236.         for (unsigned i = 0; i < nodes; i++)
  237.             V[i] = atGet(i);
  238.         V[i] = voiD0;
  239.     }
  240.     return V;
  241. }
  242.  
  243. unsigned Binder::setLimit(unsigned newLimit)
  244. {
  245.     voiDV newLinkS;
  246.     unsigned i;
  247.  
  248.     if (newLimit < nodes)
  249.         newLimit = nodes;
  250.     else if (newLimit > maxNodes)
  251.         newLimit = maxNodes;
  252.     if (newLimit < delta)
  253.         newLimit = delta;
  254.     if (!linkS || !newLimit || newLimit == limit)
  255.         return 0;
  256.     if ((newLinkS = new voiD[newLimit]) == voiDV0)
  257.         return 0;
  258.     if ((i = limit - first) > nodes)
  259.         i = nodes;
  260.     memcpy(newLinkS,&linkS[first],sizeof(linkS[0])*i);
  261.     /* copy wrap around */
  262.     if (i < nodes)
  263.         memcpy(&newLinkS[i],linkS,
  264.             sizeof(linkS[0])*(nodes-i));
  265.     if (newLimit > limit)
  266.         if (newLimit - delta > limit)
  267.             lowLimit = newLimit - delta;
  268.         else
  269.             lowLimit = limit;
  270.     else
  271.         if (newLimit - delta > delta)
  272.             lowLimit = newLimit - delta;
  273.         else
  274.             lowLimit = delta;
  275.     lowThreshold = lowLimit - delta;
  276.     delete linkS;
  277.     linkS = newLinkS;
  278.     limit = newLimit;
  279.     first = 0;
  280.     return limit;
  281. }
  282.  
  283. unsigned Binder::setDelta(unsigned newDelta)
  284. {
  285.     return ((newDelta && newDelta <= lowLimit)?
  286.         delta = newDelta : 0);
  287. }
  288.  
  289. unsigned Binder::setMaxNodes(unsigned newMaxNodes)
  290. {
  291.     return ((newMaxNodes >= limit)?
  292.         (maxNodes = (newMaxNodes
  293.         > BDR_MAXNODES)? BDR_MAXNODES
  294.         : newMaxNodes) : 0);
  295. }
  296.  
  297. voiD Binder::atIns(unsigned n, voiD D)
  298. {
  299.     voiDV newLinkS;
  300.     unsigned newLimit, i;
  301.  
  302.     if (!linkS || !D)
  303.         return voiD0;
  304.     if (nodes == limit)  {
  305.         if (limit == maxNodes)
  306.             return voiD0;
  307.         newLimit = (maxNodes - delta > limit)?
  308.             limit + delta : maxNodes;
  309.         if ((newLinkS = new voiD[newLimit])
  310.             == voiDV0) return voiD0;
  311.         if ((i = limit - first) > nodes)
  312.             i = nodes;
  313.         memcpy(newLinkS,&linkS[first],
  314.             sizeof(linkS[0])*i);
  315.         /* copy wrap around */
  316.         if (i < nodes)
  317.             memcpy(&newLinkS[i],linkS,
  318.                 sizeof(linkS[0])*(nodes-i));
  319.         /*
  320.             Compute next smaller linkS size
  321.             and threshold for shrinking.
  322.         */
  323.         lowLimit = limit;
  324.         lowThreshold = lowLimit - delta;
  325.         /* swap new for old */
  326.         delete linkS;
  327.         linkS = newLinkS;
  328.         limit = newLimit;
  329.         first = 0;
  330.     }
  331.     if (!Dattach(D))
  332.         return voiD0;
  333.     if (!n)  /* push */
  334.         linkS[first? --first
  335.             : (first = limit - 1)] = D;
  336.     else if (n >= nodes) /* insQ */
  337.         linkS[(first+(n=nodes))%limit] = D;
  338.     else  { /* insert interior */
  339.         i = (first + n) % limit;
  340.         if (i < first || !first)
  341.             /* move rear rightward */
  342.             memmove(&linkS[i+1],&linkS[i],
  343.                 sizeof(linkS[0])
  344.                 * (nodes-n));
  345.         else  { /* move front leftward */
  346.             memmove(&linkS[first-1],&linkS[first],
  347.                 sizeof(linkS[0])*(n+1));
  348.             first--;
  349.         }
  350.  
  351.         linkS[i] = D;
  352.     }
  353.     nodes++;
  354.     if (n <= curNode)
  355.         curNode++;
  356.     flags &= ~BDR_SORTED;
  357.     return D;
  358. }
  359.  
  360. voiD Binder::atInsNew(unsigned n, const voiD D)
  361. {
  362.     voiD cD;
  363.  
  364.     if (D && flags & BDR_DNEW)
  365.         if ((cD = Dnew(D)) != voiD0)
  366.             if (atIns(n,cD))
  367.                 return cD;
  368.             else
  369.                 Ddelete(cD);
  370.     return voiD0;
  371. }
  372.  
  373. voiD Binder::atRmv(unsigned n)
  374. {
  375.     voiDV newLinkS;
  376.     unsigned newLimit, i;
  377.     voiD D;
  378.  
  379.     if (!linkS || n >= nodes)
  380.         return voiD0;
  381.     D = linkS[i=(first+n)%limit];
  382.     if (!n)  {  /* pop */
  383.         if (++first >= limit)
  384.             first = 0;
  385.     }
  386.     else if (n != nodes-1)  {  /* del interior */
  387.         if (i < first)    /* move tail leftward */
  388.             memmove(&linkS[i],linkS[i+1],
  389.                 sizeof(linkS[0])*(nodes-n-1));
  390.         else {  /* move head rightward */
  391.             memmove(&linkS[first+1],&linkS[first],
  392.                 sizeof(linkS[0])*n);
  393.             first++;
  394.         }
  395.     }
  396.     if (--nodes == 0)
  397.         flags |= BDR_SORTED;
  398.     if (n < curNode)
  399.         curNode--;
  400.     else if (n == curNode)
  401.         curNode = nodes;
  402.     if (nodes < lowThreshold)  {
  403.         newLimit = lowLimit;
  404.         if ((newLinkS = new voiD[newLimit])
  405.             != voiDV0)  {
  406.             if ((i = limit - first) > nodes)
  407.                 i = nodes;
  408.             memcpy(newLinkS,&linkS[first],
  409.                 sizeof(linkS[0])*i);
  410.             /* copy wrap around */
  411.             if (i < nodes)
  412.                 memcpy(&newLinkS[i],linkS,
  413.                     sizeof(linkS[0])
  414.                     *(nodes-i));
  415.             /*
  416.                 Compute next smaller linkS
  417.                 size and threshold for
  418.                 shrinking.
  419.             */
  420.             if (lowLimit - delta > delta)
  421.                 lowLimit -= delta;
  422.             else
  423.                 lowLimit = delta;
  424.             lowThreshold = lowLimit - delta;
  425.             /* swap new for old */
  426.             delete linkS;
  427.             linkS = newLinkS;
  428.             limit = newLimit;
  429.             first = 0;
  430.         }
  431.     }
  432.     Ddetach(D);
  433.     return D;
  434. }
  435.  
  436. void Binder::allRmv()
  437. {
  438.     while (atRmv(0)) /* null stmt */ ;
  439. }
  440.  
  441. int  Binder::atDel(unsigned n)
  442. {
  443.     voiD D;
  444.  
  445.     if (flags & BDR_DDELETE)
  446.         if ((D = atRmv(n)) != voiD0)  {
  447.             Ddelete(D);
  448.             return 1;
  449.         }
  450.     return 0;
  451. }
  452.  
  453. voiD Binder::atDelAsg(unsigned n, voiD D)
  454. {
  455.     voiD S;
  456.  
  457.     if (D && flags & BDR_DASSIGN && flags & BDR_DDELETE)
  458.         if ((S = atGet(n)) != voiD0)
  459.             if (D != S) if (Dassign(D,S))  {
  460.                 (void) atDel(n);
  461.                 return D;
  462.             }
  463.     return voiD0;
  464. }
  465.  
  466. int Binder::allDel()
  467. {
  468.     voiD D;
  469.     
  470.     if (flags & BDR_DDELETE)  {
  471.         while ((D = atRmv(0)) != voiD0)
  472.             Ddelete(D);
  473.         return 1;
  474.     }
  475.     return 0;
  476. }
  477.  
  478. voiD Binder::atPut(unsigned n, voiD D)
  479. {
  480.     if (linkS && D && (n < nodes))  {
  481.         voiD& N = linkS[(first+n)%limit];
  482.         if (D != N)  if (Dattach(D))  {
  483.             flags &= ~BDR_SORTED;
  484.             Ddetach(N);
  485.             if (flags & BDR_DDELETE)
  486.                 Ddelete(N);
  487.             return (N=D);
  488.         }
  489.     }
  490.     return voiD0;
  491. }
  492.  
  493. voiD Binder::atPutNew(unsigned n, const voiD D)
  494. {
  495.     voiD oldD, cD;
  496.  
  497.     if (!D || !(flags & BDR_DNEW))
  498.         return voiD0;
  499.     if ((oldD = atGet(n)) == voiD0)
  500.         return voiD0;
  501.     if (oldD == D)
  502.         return voiD0;
  503.     if ((cD = Dnew(D)) != voiD0)
  504.         if (atPut(n,cD))
  505.             return cD;
  506.         else
  507.             Ddelete(cD);
  508.     return voiD0;
  509. }
  510.  
  511. voiD Binder::atPutAsg(unsigned n, const voiD D)
  512. {
  513.     voiD oldD;
  514.  
  515.     if (D && flags & BDR_DASSIGN)
  516.         if ((oldD = atGet(n)) != voiD0)
  517.             if (D != oldD)
  518.                 return Dassign(oldD,D);
  519.     return voiD0;
  520. }
  521.  
  522. voiD Binder::atGet(unsigned n)
  523. {
  524.     return ((linkS && (n < nodes))?
  525.         linkS[(first+n)%limit] : voiD0);
  526. }
  527.  
  528. voiD Binder::atGetAsg(unsigned n, voiD D)
  529. {
  530.     voiD N;
  531.  
  532.     if (D && flags & BDR_DASSIGN)
  533.         if ((N = atGet(n)) != voiD0)
  534.             if (D != N)
  535.                 return Dassign(D,N);
  536.     return voiD0;
  537. }
  538.  
  539. voiD Binder::atXchg(unsigned n, voiD D)
  540. {
  541.     if (linkS && D && (n < nodes))
  542.         if (Dattach(D))  {
  543.             flags &= ~BDR_SORTED;
  544.             voiD& N = linkS[(first+n)%limit];
  545.             voiD oldD = N;
  546.             N = D;
  547.             Ddetach(oldD);
  548.             return oldD;
  549.         }
  550.     return voiD0;
  551. }
  552.  
  553. unsigned Binder::index(const voiD D)
  554. {
  555.     unsigned i;
  556.  
  557.     if (linkS && D)
  558.         for (i = 0; i < nodes; i++)
  559.             if (D == linkS[(first+i)%limit])
  560.                 return i;
  561.     return BDR_NOTFOUND;
  562. }
  563.  
  564. int Binder::forEach(BDRapplY B, voiD M, voiD A)
  565. {
  566.     unsigned i;
  567.  
  568.     if (!linkS || !B || !nodes)
  569.         return 0;
  570.     for (i = 0; i < nodes; i++)
  571.         (*B)(linkS[(first+i)%limit],M,A);
  572.     return 1;
  573. }
  574.  
  575. unsigned Binder::CurNode()
  576. {
  577.     return ((curNode < nodes)?
  578.         curNode : BDR_NOTFOUND);
  579. }
  580.  
  581. int  Binder::setCurNode(unsigned n)
  582. {
  583.     return ((curNode = ((n > nodes)? nodes : n))
  584.         < nodes);
  585. }
  586.  
  587. voiD Binder::ins(voiD D)
  588. {
  589.     if (atIns(curNode+1,D))  {
  590.         if (++curNode >= nodes)
  591.             curNode = nodes - 1;
  592.         return D;
  593.     }
  594.     return voiD0;
  595. }
  596.  
  597. voiD Binder::insNew(const voiD D)
  598. {
  599.     voiD cD;
  600.  
  601.     if (D && flags & BDR_DNEW)
  602.         if ((cD = Dnew(D)) != voiD0)
  603.             if (ins(cD))
  604.                 return cD;
  605.             else
  606.                 Ddelete(cD);
  607.     return voiD0;
  608. }
  609.  
  610. voiD Binder::rmv()
  611. {
  612.     voiD D;
  613.     unsigned n;
  614.  
  615.     if ((D = atRmv(n=curNode)) != voiD0)
  616.         if (n--)
  617.             curNode = n;
  618.     return D;
  619. }
  620.  
  621. int  Binder::del()
  622. {
  623.     voiD D;
  624.     
  625.     if (flags & BDR_DDELETE)
  626.         if ((D = rmv()) != voiD0)  {
  627.             Ddelete(D);
  628.             return 1;
  629.         }
  630.     return 0;
  631. }
  632.  
  633. voiD Binder::delAsg(voiD D)
  634. {
  635.     voiD S;
  636.  
  637.     if (D && flags & BDR_DASSIGN && flags & BDR_DDELETE)
  638.         if ((S = atGet(curNode)) != voiD0)
  639.             if (D != S) if (Dassign(D,S))  {
  640.                 (void) del();
  641.                 return D;
  642.             }
  643.     return voiD0;
  644. }
  645.  
  646. voiD Binder::next()
  647. { 
  648.     if (linkS)  {
  649.         if (curNode >= nodes)
  650.             curNode = 0;
  651.         else
  652.             curNode++;
  653.         if (curNode < nodes)
  654.             return linkS[(first+curNode)%limit];
  655.     }
  656.     return voiD0;
  657. }
  658.  
  659. voiD Binder::nextAsg(voiD D)
  660. {
  661.     unsigned oldCurNode = curNode;
  662.     voiD S;
  663.  
  664.     if (D && flags & BDR_DASSIGN)
  665.         if ((S = next()) != voiD0)  {
  666.             if (D != S) if (Dassign(D,S))
  667.                 return D;
  668.             curNode = oldCurNode;
  669.         }
  670.     return voiD0;
  671. }
  672.  
  673. voiD Binder::prev()
  674. { 
  675.     if (linkS)  {
  676.         if (curNode)  {
  677.             if (curNode > nodes)
  678.                 curNode = nodes;
  679.             curNode--;
  680.         }
  681.         else
  682.             curNode = nodes;
  683.         if (curNode < nodes)
  684.             return linkS[(first+curNode)%limit];
  685.     }
  686.     return voiD0;
  687. }
  688.  
  689. voiD Binder::prevAsg(voiD D)
  690. {
  691.     unsigned oldCurNode = curNode;
  692.     voiD S;
  693.  
  694.     if (D && flags & BDR_DASSIGN)
  695.         if ((S = prev()) != voiD0)  {
  696.             if (D != S) if (Dassign(D,S))
  697.                 return D;
  698.             curNode = oldCurNode;
  699.         }
  700.     return voiD0;
  701. }
  702.  
  703. voiD Binder::firstThat(BDRdetecT B, voiD M)
  704. {
  705.     if (linkS && B && nodes)
  706.         for (curNode = 0;
  707.             curNode < nodes;
  708.             curNode++)  {
  709.             voiD N = linkS[(first+curNode)
  710.                 %limit];
  711.             if ((*B)(N,M))
  712.                 return N;
  713.         }
  714.     return voiD0;
  715. }
  716.  
  717. voiD Binder::lastThat(BDRdetecT B, voiD M)
  718. {
  719.     if (linkS && B && nodes)  {
  720.         curNode = nodes;
  721.         while (curNode--)  {
  722.             voiD N = linkS[(first+curNode)
  723.                 %limit];
  724.             if ((*B)(N,M))
  725.                 return N;
  726.         }
  727.         curNode = nodes;
  728.     }
  729.     return voiD0;
  730. }
  731.  
  732. int   Binder::sort(BDRcomP comP)
  733. {
  734.     unsigned low, mid, high;
  735.     unsigned d;
  736.     voiD D;
  737.  
  738. /*
  739.     The current node is always reset to undefined
  740.     regardless of the outcome of sort.
  741. */
  742.  
  743.     curNode = nodes;
  744.     if (flags & BDR_SORTED)  {
  745.         if (this->comP == comP || !comP)
  746.             return 1;
  747.     }
  748.     else if (!this->comP && !comP)
  749.         return 0;
  750.     if (comP)  {
  751.         this->comP = comP;
  752.         flags &= ~BDR_SORTED;
  753.     }
  754.     if (!nodes)
  755.         return (int) (flags |= BDR_SORTED);
  756.     if (!linkS)
  757.         return 0;
  758.     if (first)  { /* form contiguous block at front */
  759.         d = (first + nodes) % limit;
  760.         if (d > first)
  761.             memmove(linkS,&linkS[first],
  762.                 sizeof(linkS[0])*nodes);
  763.         else if (d < first)
  764.             memmove(&linkS[d],&linkS[first],
  765.                 sizeof(linkS[0])
  766.                 *(limit-first));
  767.         /* else array is full/contiguous */
  768.         first = 0;
  769.     }
  770.     for (high = d = 1; d < nodes; high = ++d)  {
  771.         low = 0;
  772.         D = linkS[d];
  773.         while (low < high)  {
  774.             mid = low + ((high - low) >> 1);
  775.             if ((*this->comP)(D,
  776.                 linkS[mid]) <= 0)
  777.                 high = mid;
  778.             else
  779.                 low = mid + 1;
  780.         }
  781.         if (high < d)  {
  782.             memmove(&linkS[high+1],&linkS[high],
  783.                 sizeof(linkS[0])*(d-high));
  784.             linkS[high] = D;
  785.         }
  786.     }
  787.     return (int) (flags |= BDR_SORTED);
  788. }
  789.  
  790. voiD Binder::insSort(voiD D)
  791. {
  792.     unsigned low, mid, high;
  793.     voiD ok;
  794.  
  795. /*
  796.     The current node is left undefined if
  797.     anything fails, otherwise it is set to the
  798.     newly inserted node.
  799. */
  800.  
  801.     curNode = nodes;
  802.     if (!linkS || !D || nodes >= maxNodes || !comP)
  803.         return voiD0;
  804.     if (!(flags & BDR_SORTED))
  805.         if (!sort())
  806.             return voiD0;
  807.     low = 0;
  808.     high = nodes;
  809.     while (low < high)  {
  810.         mid = low + ((high - low) >> 1);
  811.         if ((*comP)(D,
  812.             linkS[(first+mid)%limit]) <= 0)
  813.             high = mid;
  814.         else
  815.             low = mid + 1;
  816.     }
  817.     if ((ok = atIns(high,D)) != voiD0)
  818.         curNode = high;
  819.     /*  atIns() resets sorted to zero  */
  820.     flags |= BDR_SORTED;
  821.     return ok;
  822. }
  823.  
  824. voiD Binder::insSortNew(const voiD D)
  825. {
  826.     voiD cD;
  827.  
  828.     if (D && flags & BDR_DNEW)
  829.         if ((cD = Dnew(D)) != voiD0)
  830.             if (insSort(cD))
  831.                 return cD;
  832.             else
  833.                 Ddelete(cD);
  834.     return voiD0;
  835. }
  836.  
  837. voiD Binder::insUnique(voiD D)
  838. {
  839.     if (comP) if (!findFirst(D))
  840.         return insSort(D);
  841.     curNode = nodes;
  842.     return voiD0;
  843. }
  844.  
  845. voiD Binder::insUniqueNew(const voiD D)
  846. {
  847.     if (comP && flags & BDR_DNEW)
  848.         if (!findFirst(D))
  849.             return insSortNew(D);
  850.     curNode = nodes;
  851.     return voiD0;
  852. }
  853.  
  854. voiD Binder::findFirst(const voiD K)
  855. {
  856.     unsigned low, mid, high;
  857.     voiD D;
  858.  
  859. /*
  860.     The current node is left undefined if
  861.     anything fails, otherwise it is set to the
  862.     newly found node.
  863. */
  864.  
  865.     curNode = nodes;
  866.     if (!linkS || !K || !comP || !nodes)
  867.         return voiD0;
  868.     if (flags & BDR_SORTED)  {
  869.         low = 0;
  870.         high = nodes;
  871.         while (low < high)  {
  872.             mid = low + ((high - low) >> 1);
  873.             if ((*comP)(K,linkS[(first+mid)
  874.                 %limit]) <= 0)
  875.                 high = mid;
  876.             else
  877.                 low = mid + 1;
  878.         }
  879.         if (high < nodes)
  880.             if (!(*comP)(K,D=linkS[(first+
  881.                 high)%limit]))  {
  882.                 curNode = high;
  883.                 return D;
  884.             }
  885.     }
  886.     else  {  /*  linear search!  */
  887.         while ((D = next()) != voiD0)
  888.             if (!(*comP)(K,D))
  889.                 return D;
  890.     }
  891.     return voiD0;
  892. }
  893.  
  894. voiD Binder::findNext(const voiD K)
  895. {
  896.  
  897. /*
  898.     For sorted binders you must first call findFirst()
  899.     to insure consistent results!
  900. */
  901.  
  902.     voiD D;
  903.  
  904. /*
  905.     The current node is left undefined if
  906.     anything fails, otherwise it is set to the
  907.     newly found node.
  908. */
  909.  
  910.     if (!linkS || !K || !comP)  {
  911.         curNode = nodes;
  912.         return voiD0;
  913.     }
  914.     while ((D = next()) != voiD0)
  915.         if (!(*comP)(K,D))
  916.             return D;
  917.         else if (flags & BDR_SORTED)  {
  918.             curNode = nodes;
  919.             break; /*  Look no further!  */
  920.         }
  921.     return voiD0;
  922. }
  923.  
  924. voiD Binder::findLast(const voiD K)
  925. {
  926.     unsigned low, mid, high;
  927.     voiD D;
  928.  
  929. /*
  930.     The current node is left undefined if
  931.     anything fails, otherwise it is set to the
  932.     newly found node.
  933. */
  934.  
  935.     curNode = nodes;
  936.     if (!linkS || !K || !comP || !nodes)
  937.         return voiD0;
  938.     if (flags & BDR_SORTED)  {
  939.         low = 0;
  940.         high = nodes;
  941.         while (low < high)  {
  942.             mid = low + ((high - low) >> 1);
  943.             if ((*comP)(K,linkS[(first+mid)
  944.                 %limit]) < 0)
  945.                 high = mid;
  946.             else
  947.                 low = mid + 1;
  948.         }
  949.         if (high < nodes)
  950.             if (!(*comP)(K,D=linkS[(first+
  951.                 high)%limit]))  {
  952.                 curNode = high;
  953.                 return D;
  954.             }
  955.     }
  956.     else  {  /*  linear search!  */
  957.         while ((D = prev()) != voiD0)
  958.             if (!(*comP)(K,D))
  959.                 return D;
  960.     }
  961.     return voiD0;
  962. }
  963.  
  964. voiD Binder::findPrev(const voiD K)
  965. {
  966.  
  967. /*
  968.     For sorted binders you must first call findLast()
  969.     to insure consistent results!
  970. */
  971.  
  972.     voiD D;
  973.  
  974. /*
  975.     The current node is left undefined if
  976.     anything fails, otherwise it is set to the
  977.     newly found node.
  978. */
  979.  
  980.     if (!linkS || !K || !comP)  {
  981.         curNode = nodes;
  982.         return voiD0;
  983.     }
  984.     while ((D = prev()) != voiD0)
  985.         if (!(*comP)(K,D))
  986.             return D;
  987.         else if (flags & BDR_SORTED)  {
  988.             curNode = nodes;
  989.             break; /*  Look no further!  */
  990.         }
  991.     return voiD0;
  992. }
  993.  
  994. unsigned Binder::findAll(const voiD K)
  995. {
  996.     unsigned count = 0;
  997.  
  998.     /*  The current node is left undefined.  */
  999.     
  1000.     if (findFirst(K))
  1001.         do { 
  1002.             count++;
  1003.         } while (findNext(K));
  1004.     return count;
  1005. }
  1006.  
  1007. ostream& BDRendm(ostream& os)
  1008. {
  1009.     return os << Binder::memberTermChar << flush;
  1010. }
  1011.  
  1012. istream& BDRnextm(istream& is)
  1013. {
  1014.     is.get();
  1015.     return is;
  1016. }
  1017.